Field of the Invention
This invention relates generally to the field of computer processors. More particularly, the invention relates to an apparatus and method for loop-invariant instruction detection and deletion.
Description of the Related Art
In computer programming, loop-invariant code consists of statements or expressions in a loop that do not change from iteration to iteration. This means that loop-invariant code may be moved outside the body of a loop to be computed at once without affecting the semantics of the computer program. Loop-Invariant Code Motion (LICM), a computer optimization that performs this movement automatically, is one of the most widely used compiler optimizations in computer architecture. However, in many cases, a compiler is unable to perform this advantageous optimization due to reasons such as: 1) lack of architectural registers to keep track of all the loop-invariant values; 2) inability to prove loop invariance because of unresolved memory conflicts (i.e., compiler is unable to prove that loads within the loop are not colliding with other store references); and/or 3) loop invariance's dependence on the control flow (i.e., loop invariance is conditional and known only at runtime). Moreover, all currently known solutions require binary translation assisted micro-architecture and assist of software compiler to perform loop-invariant code detection and elimination that are complicated and costly to implement.